//找连续子序列最大的长度
#include <iostream>
#include <vector>
#include <unordered_set>

class Solution {
public:
    int longestConsecutive(std::vector<int>& nums) 
    {
        //生成哈希表
        std::unordered_set<int> hash(nums.begin(), nums.end());
        //遍历哈希表
        int max_length  = 0;
        for(auto num : hash)
        {
            //判断该数前面的数字存不存在，如果存在的话，就不是一个连续的子序列的开始
            //不存在的话，就说明是，则进入if内部开始统计长度
            if(hash.find(num - 1) == hash.end())
            {
                int current_num = num;
                int length = 1;
                //这里的时间复杂度不是N方，while循环的内部操作find、以及++都可以说是常数级别的操作
                while(hash.find(current_num + 1) != hash.end())
                {
                    current_num++;
                    length++;
                }
                max_length = std::max(length, max_length);
            }
        }
        return max_length;
    }
};

//不适用vector作为哈希表的原因是会超时，当一个数组的跨度比较大的时候，
//例如有10000个数字，但是最小值和最大值超过了100万的跨度，那么最后统计的时候
//遍历这个哈希表，就不是O（N）的时间复杂度了